package 递归or回溯;
import java.util.*;

/**
 * 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
 */
public class letterCombinations {
    // 存储数字到字母的映射关系
    static HashMap<Character, String> map = new HashMap<>();
    // 存储最终结果
    static List<String> ans = new ArrayList<>();
    // 用于构建当前组合的临时字符串
    static StringBuilder sb = new StringBuilder();

    /**
     * 主方法：处理输入并返回所有可能的字母组合
     * @param digits 输入的数字字符串
     * @return 所有可能的字母组合列表
     */
    public static List<String> letterCombinationsM(String digits){
        // 处理空输入的情况
        if(digits.isEmpty())
            return ans;
        
        // 初始化数字到字母的映射
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        
        // 开始回溯搜索
        backTracking(digits, 0);
        return ans;
    }

    /**
     * 回溯方法：递归生成所有可能的字母组合
     * @param digits 输入的数字字符串
     * @param begin 当前处理的数字位置
     */
    private static void backTracking(String digits, int begin){
        // 当处理完所有数字时，将当前组合加入结果列表
        if(begin == digits.length()){
            ans.add(sb.toString());
            return;
        }

        // 获取当前数字对应的字母集合
        char c = digits.charAt(begin);
        String s = map.get(c);
        
        // leetcode核心代码模式需要去掉static修饰词
        // static修饰后，内部只能调用static修饰过的方法或变量
        // 回溯：添加->递归->删除
        // 例：输入23，从map中获取对应位置字母
        // c = digits.charAt(0) = digits[0] = '2'
        // s = map.get('2') = 'abc'
        // ch = 'a', 'b', 'c'
        // sb.append('a') = 'a'
        // backTracking(digits, 1)
        // c = digits.charAt(1) = digits[1] = '3'
        // s = map.get('3') = 'def'
        // ch = 'd', 'e', 'f'
        // sb.append('d') = 'ab'
        // backTracking(digits, 2)
        // begin = 2 = digits.length()
        // ans.add(sb.toString()) = 'ab'
        // sb.deleteCharAt(sb.length() - 1) = 'a'
        // sb.append('e') = 'ae'
        // ...
        // 遍历当前数字对应的所有字母
        for(char ch : s.toCharArray()){
            // 添加当前字母到组合中
            sb.append(ch);
            // 递归处理下一个数字
            backTracking(digits, begin + 1);
            // 回溯：移除最后添加的字母
            sb.deleteCharAt(sb.length() - 1);
        }
        // void函数会隐式返回，可以不加return;
        // return;
    }

    /**
     * 主函数：处理输入输出
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(letterCombinationsM(s));
        sc.close();
    }
}
